// https://www.lintcode.com/problem/inorder-successor-in-bst/description

// 448. 二叉查找树的中序后继
// 给定一个二叉查找树(什么是二叉查找树)，以及一个节点，求该节点在中序遍历的后继，如果没有返回null

// 样例
// 给出 tree = [2,1] node = 1:

//   2
//  /
// 1
// 返回 node 2.

// 给出 tree = [2,1,3] node = 2:

//   2
//  / \
// 1   3
// 返回 node 3.

// 挑战
// O(h)，其中h是BST的高度。

// 注意事项
// 保证p是给定二叉树中的一个节点。(您可以直接通过内存地址找到p)




/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 


class Solution {
public:
    /*
     * @param root: The root of the BST.
     * @param p: You need find the successor node of p.
     * @return: Successor of p.
     */
    
    // 中序遍历做法，不管是不是二叉查找树（个）
    // TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
    //     stack<TreeNode *> s;
    //     vector<TreeNode *> v;
    //     while (root || !s.empty())
    //     {
    //         while (root)
    //         {
    //             s.push(root);
    //             root = root->left;
    //         }
    //         root = s.top();
    //         s.pop();
    //         if (!v.empty() && v.back() == p)
    //         {
    //             return root;
    //         }
    //         v.push_back(root);
    //         root = root->right;
    //     }
    //     return NULL;
    // }
    
    // O(h-tree):二分查找，注意parent已经记住了，就是root
    // 递归
    // TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
    //     if (!root)
    //     {
    //         return NULL;
    //     }
    //     if (p->val < root->val) // p的值＜root的值，后继可能是root(往后递归找不到后继)
    //     {
    //         TreeNode * left = inorderSuccessor(root->left, p);
    //         return left == NULL ? root: left;
    //     }
    //     else // p的值≥root的值，后继和root没什么关系
    //     {
    //         return inorderSuccessor(root->right, p);
    //     }
    // }
    
    // 非递归 需要用cand记住，因为不能把下一步的结果拿到这一步来判断
    TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
        TreeNode * cand = NULL; 
        while (root)
        {
            if (p->val < root->val)
            {
                cand = root; // cand只记比p大的时候的数
                root = root->left;
            }
            else
            {
                root = root->right;
            }
        }
        return cand;
    }
};